package leetcode_41_60;

public class trap_42 {

    /**
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，
     * 计算按此排列的柱子，下雨之后能接多少雨水。
     * 思路是有凹陷才能蓄水，找寻所有极值点
     * 关键是其中存在连续相等的极值点
     * 思路失败
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int[] point = new int[height.length];  //第一个高点开始所有的极值点坐标
        int point_index = 0, t = 1;
        int last_min = 0, last_max = 0;             //记录上一个更大或更小的数，防止连续数字
        boolean isplus = true;        //是否升序
        for (; t < height.length - 1; t++) {        //不判断最后一个
            if (height[t] == height[t + 1])  //只判断连续等值的最后一个数字
                continue;
            isplus = height[t] < height[t + 1];
            if (isplus) {
                if (height[t] > last_max && height[t] > height[t + 1])              //是极大值点
                    point[point_index++] = t;
                else
                    last_max = height[t];
            } else {
                if (height[t] < last_min && height[t] < height[t + 1])              //是极小值点
                    point[point_index++] = t;
                else
                    last_min = height[t];
            }
        }
        //判断最后一位
        if (isplus) {
            if (height[t] > last_max)              //是极大值点
                point[point_index++] = t;
        } else {
            if (height[t] < last_min)              //是极小值点
                point[point_index++] = t;
        }
        return point_index;
    }

    /**
     * 可以按列求求每一列能够放多少水
     * 我们只需要关注当前列，以及左边最高的墙，右边最高的墙就够了。
     * 先用动态规划
     */
    public int trap2(int[] height) {
        int sum = 0;
        int[] max_left = new int[height.length];     // 每个位置它的左边最大高度
        int[] max_right = new int[height.length];  // 每个位置它的右边最大高度

        for (int i = 1; i < height.length - 1; i++) {
            //只需要与前一个的左边最大高度与前一个相比较即可得到该位置左边最大高度
            max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
        }
        for (int i = 1; i < height.length - 1; i++) {
            int min = Math.min(max_left[i], max_right[i]);
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }

    /**
     * 双指针
     * 毕竟求出每个位置的左右最大高度还是会有很多多余计算
     * 希望跟随循环进行实时的动态规划，不采用提前计算的方式
     *
     * 需要解决的问题
     * for 循环是从左到右遍历的
     * max_left 易进行操作，
     * 而 max_right 的更新是从右向左的。
     *
     * 需要两个指针从两个方向去遍历
     * 如果 max_left  大于  max_right 时，从右向左遍历
     * 因为此时max_right一定小于right左侧最小的元素
     * 对于右边的元素来说左部分无需考虑，只需动态规划max_right 即可
     * 反之对应
     *
     * @param height
     * @return
     */
    public int trap3(int[] height) {
        int sum = 0;
        int max_left = 0;         //左指针左侧的最大值
        int max_right = 0;      //右指针右侧的最大值
        int left = 1;
        int right = height.length - 2; // 加右指针进去
        while(left <= right){
            max_left = Math.max(max_left, height[left - 1]);
            max_right = Math.max(max_right, height[right + 1]);
            //从左到右更
            if (max_left < max_right) {
                if (max_left> height[left]) {
                    sum = sum + (max_left - height[left]);
                }
                left++;
            }
            // 如果 max_left  大于  max_right 时，从右向左遍历
            // 因为此时max_right一定小于right左侧最大的元素
            // 左部分无需考虑，只需动态规划max_right 即可
            else {
                if (max_right  > height[right]) {         //当右侧最大值大于该位置时，这一列才能蓄水
                    sum = sum + (max_right  - height[right]);
                }
                right--;
            }
        }
        return sum;
    }
}
